package com.lz.learning;

import java.util.ArrayList;
import java.util.List;

/**
 * 烧饼排序
 * <p>
 * in:  [3,2,4,1]
 * <p>
 * out: [4,2,4,3]
 * <p>
 * 4:[1,4,2,3]
 * 2:[4,1,2,3]
 * 4;[3,2,1,4]
 * 3:[1,2,3,4]
 */
public class CakeSolution {
    public static void main(String[] args) {

    }

    List<Integer> res = new ArrayList<>();

    /**
     * bug: 假设数组长度为 n 则会翻2(n-1)次，这是个问题
     * @param array
     * @param length 数组下标，length = array.length-1
     */
    void sort(int[] array, int length) {

        if (length == 1) return;
        // 1、先找到最大的个数
        int max = 0X80000000;
        int pos = -1;
        for (int i = 0; i <= length; i++) {
            int temp = array[i];
            if (temp > max) {
                max = temp;
                pos = i;
            }
        }
        // 已经在最后一个位置不需要
        if (pos != length) {
            // 2、翻到最上面
            reverse(array, pos);
            res.add(pos + 1);
            // 翻转整个数组
            reverse(array, length);
            res.add(length + 1);
        }

        // 递归
        sort(array, length - 1);

    }

    void reverse(int[] array, int end) {
        int i = 0, j = end;
        while (i < j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }
    }
}
